Union and intersection of regular languages – the product construction
Given a word w\in \{a,b\}^*, let L_w=\{xwy\mid x,y\in\{a,b\}^*\}. In other words, L_w is the language of all words containing w as a subword.
Show that for every word w, L_w is a regular language.
Construct minimum DFAs recognizing the following languages. Show that the constructed DFAs are correct and have the smallest possible number of states.
- L_{a}
- L_{aa}
- L_{aaa}
Using the cartesian product construction, construct DFAs recognizing the following languages and minimize the DFAs obtained.
- L_{aa}\cup L_{bb}
- L_{a}\cup L_{bbb}
What would change if we wanted the languages L_{aa}\cap L_{bb} and L_{a}\cap L_{bbb} instead?
Given two DFAs A and B as input, what is the cost of computing a DFA for L(A)\cup L(B) and L(A)\cap L(B) using the cartesian product construction?
Given minimum DFAs A and B, is the DFA recognizing L(A)\cup L(B) obatained applying the product construction on A and B minimum? What about the DFA for L(A)\cap L(B)?
What happens if we apply the cartesian product construction to NFAs instead of DFAs? Does the product construction on NFAs still give a good NFA for the union (resp. intersection)?